// Package sort
// 排序算法实现, 从小打大排序
// 包括了 冒泡排序，选择排序，插入排序，希尔排序
// 快速排序,堆排序,归并排序,计数排序（未实现）,桶排序,基数排序
package sort

import (
	"time"
	"math/rand"
)

// SorterInterface 需要排序的struct要实现的接口
type SorterInterface interface {
	GetSorter() int
}

// BubbleSort 冒泡排序
func BubbleSort(li []SorterInterface) {
	for i := 0; i < len(li)-1; i++ {
		exchange := false
		for j := 0; j < len(li)-i-1; j++ {
			if li[j].GetSorter() > li[j+1].GetSorter() {
				li[j], li[j+1] = li[j+1], li[j]
				exchange = true
			}
		}
		if !exchange {
			return
		}
	}
}


// SelectSort 选择排序
func SelectSort(li []SorterInterface) {
	for i := 0; i < len(li)-1; i++ {
		pos := i
		for j := i + 1; j < len(li); j++ {
			if li[pos].GetSorter() > li[j].GetSorter() {
				pos = j
			}
		}
		li[i], li[pos] = li[pos], li[i]
	}
}

// 插入排序
func InsertSort(li []SorterInterface) {
	for i := 1; i < len(li); i++ {
		tmp := li[i]
		j := i - 1
		for j >= 0 && tmp.GetSorter() < li[j].GetSorter() {
			li[j+1] = li[j]
			j --
		}
		li[j+1] = tmp
	}
}

// ShellSort 希尔排序
func ShellSort(li []SorterInterface) {
	for gap := len(li) / 2; gap > 0; gap /= 2 {
		for i := gap; i < len(li); i++ {
			tmp := li[i]
			j := i - gap
			for j >= 0 && tmp.GetSorter() < li[j].GetSorter() {
				li[j+gap] = li[j]
				j -= gap
			}
			li[j+gap] = tmp
		}
	}
}

// QuickSort 快速排序
func QuickSort(li []SorterInterface, left, right int) {
	if left >= right {
		return
	}
	i := left
	j := right
	rand.Seed(time.Now().Unix())
	r := rand.Intn(right-left) + left
	li[i], li[r] = li[r], li[i]
	tmp := li[i]
	for i < j {
		for i < j && li[j].GetSorter() >= tmp.GetSorter() {
			j--
		}
		li[i] = li[j]
		for i < j && li[i].GetSorter() <= tmp.GetSorter() {
			i++
		}
		li[j] = li[i]
	}
	li[i] = tmp
	QuickSort(li, left, i-1)
	QuickSort(li, i+1, right)
}

func sift(li []SorterInterface, low, high int) {
	i := low
	j := 2*i + 1
	tmp:=li[i]
	for j <= high {
		if j < high && li[j].GetSorter() < li[j+1].GetSorter() {
			j++
		}
		if tmp.GetSorter() < li[j].GetSorter() {
			li[i]  = li[j]
			i = j
			j = 2*i + 1
		} else {
			break
		}
	}
	li[i] = tmp
}

// HeapSort 堆排序
func HeapSort(li []SorterInterface) {
	for i := len(li)/2 - 1; i >= 0; i-- {
		sift(li, i, len(li)-1)
	}
	for j := len(li) - 1; j > 0; j-- {
		li[0], li[j] = li[j], li[0]
		sift(li, 0, j-1)
	}
}


func merge(li []SorterInterface, left, mid, right int) {
	i := left
	j := mid + 1
	var tmp []SorterInterface
	for i <= mid && j <= right {
		if li[i].GetSorter() <= li[j].GetSorter() {
			tmp = append(tmp, li[i])
			i ++
		} else {
			tmp = append(tmp, li[j])
			j ++
		}
	}
	if i <= mid {
		tmp = append(tmp, li[i:mid+1]...)
	} else {
		tmp = append(tmp, li[j:right+1]...)
	}
	for k := 0; k < len(tmp); k++ {
		li[left+k] = tmp[k]
	}
}

// MergeSort 归并排序
func MergeSort(li []SorterInterface, left, right int) {
	if left < right {
		mid := (left + right) / 2
		MergeSort(li, left, mid)
		MergeSort(li, mid+1, right)
		merge(li, left, mid, right)
	}
}

// CountSort 计数排序(未实现，将返回原切片)
func CountSort(li []SorterInterface) {
	//max_num := li[0].GetSorter()
	//for i := 1; i < len(li); i++ {
	//	if max_num < li[i].GetSorter() {
	//		max_num = li[i].GetSorter()
	//	}
	//}
	//arr := make([]int, max_num+1)
	//for j := 0; j < len(li); j++ {
	//	arr[li[j].GetSorter()]++
	//}
	//k := 0
	//for m, n := range arr {
	//	for p := 0; p < n; p++ {
	//		li[k] = m
	//		k++
	//	}
	//}
}

// BinSort桶排序
func BinSort(li []SorterInterface, bin_num int) {
	minNum, maxNum := li[0], li[0]
	for i := 0; i < len(li); i++ {
		if minNum.GetSorter() > li[i].GetSorter() {
			minNum = li[i]
		}
		if maxNum.GetSorter() < li[i].GetSorter() {
			maxNum = li[i]
		}
	}
	bin := make([][]SorterInterface, bin_num)
	for j := 0; j < len(li); j++ {
		n := (li[j].GetSorter() - minNum.GetSorter()) / ((maxNum.GetSorter() - minNum.GetSorter() + 1) / bin_num)
		bin[n] = append(bin[n], li[j])
		k := len(bin[n]) - 2
		for k >= 0 && li[j].GetSorter() < bin[n][k].GetSorter() {
			bin[n][k+1] = bin[n][k]
			k--
		}
		bin[n][k+1] = li[j]
	}
	o := 0
	for p, q := range bin {
		for t := 0; t < len(q); t++ {
			li[o] = bin[p][t]
			o++
		}
	}
}